package com.leetcode.algs4.graph.least_path;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Dennis Li
 * @date 2020/6/19 11:23
 */
public class BellmanFordSP {
    private double[] distTo;
    private DirectedEdge[] edgeTo;
    private boolean[] onQ;
    // 正在被放松的顶点
    private Queue<Integer> queue;
    // relax的调用次数
    private int cost;
    // 检测是否有负权重环
    private Iterable<DirectedEdge> cycle;

    public BellmanFordSP(EdgeWeightedDigraph G, int s) {
        distTo = new double[G.V()];
        edgeTo = new DirectedEdge[G.V()];
        onQ = new boolean[G.V()];
        queue = new LinkedList<>();
        //初始化各边，以进行放松操作
        for (int v = 0; v < G.V(); v++) {
            distTo[v] = Double.POSITIVE_INFINITY;
        }
        distTo[s] = 0.0;
        // 将起点入队，只要入队，设置onQ为true
        queue.offer(s);
        onQ[s] = true;
        // 队列非空，且不含有负权重环 -- 不然会陷入无限循环
        while (!queue.isEmpty() && !hasNegativeCycle()){
            int v = queue.poll();
            onQ[v] = false;
            // 每次循环，将顶点的出边进行放松
            relax(G, v);
        }

    }

    private void relax(EdgeWeightedDigraph G, int v) {
        for (DirectedEdge e : G.adj(v)) {
            int w = e.to();
            if(distTo[w] > distTo[v] + e.weight()){
                distTo[w] = distTo[v] + e.weight();
                edgeTo[w] = e;
                // 如果发生了变化，那么将这个结点入队
                // 其他distTo不发生变化的结点以后也不会改变
                if(!onQ[w]){
                    queue.offer(w);
                    onQ[w] = true;
                }
            }
            if(cost++ % G.V() == 0){
                // 当遍历的次数达到V时，进行负权重的检测
                findNegativeCycle();
            }
        }
    }

    private void findNegativeCycle() {
        int V = edgeTo.length;
        EdgeWeightedDigraph spt = new EdgeWeightedDigraph(V);
        for (int v = 0; v < V; v++) {
            if(edgeTo[v] != null)
                spt.addEdge(edgeTo[v]);
        }
        EdgeWeightedDirectedCycle cf = new EdgeWeightedDirectedCycle(spt);
        cycle = cf.cycle();
    }

    public boolean hasNegativeCycle() {
        return cycle != null;
    }

    public Iterable<DirectedEdge> negativeCycle(){
        return cycle;
    }
}
